The present invention relates to computer memories and, more specifically to methods and devices for adapting computer memories to computer network applications.
Computer memories have been used in computers since computers were first invented. The advent of networks of computers has provided another field in which computer memories can be used. The increasing rates of data influx in networks has underlined the difference between how computers and networks use computer memories. Previously, high speed yet costly SRAM (Static Random Access Memories) were used in buffers in computer network elements to help the networks cope with fast input and throughput of data in networks. In recent years cheap yet faster and faster DRAMs (dynamic random access memory) have taken some of the duties of the SRAM. Because of its cost, this DRAM type of computer memory is, currently the most widely used type of computer memory in regular computers. However, as noted above, computers and network devices use computer memory in different ways.
While regular computers and network devices try to take advantage of the large storage capacities and fast access times offered by DRAMs, the patterns of use of computer memories is different. For computing applications, long, variable bursts of data are not uncommon. Furthermore, the amount of data accessed in read/write memory access operations and the ratio between read memory access operations and write memory access operations is dependent on the actual computer application. Also, computer applications may require that computer memories be able to transfer large amounts of data in a short amount of time even though normal computer applications generally only use moderate amounts of data flow. And lastly, data delay, or the delay between bursts of data, is not a high priority for computer applications.
In contrast to the above, networking applications, as implemented in network devices, have very different requirements. Networking applications generally require short, fixed length blocks of data from the computer memories. The amount of data per unit time that computer memories have to deliver is dictated by datapath speeds and there are usually equal numbers of read and write memory access operations. Furthermore, networking applications require that a guaranteed amount of data be delivered in a given time to maintain datapaths. In terms of data delays, delays must be predictable and minimizing such delays is highly desirable.
One major development in the field of DRAMs is the emergence of the RDRAM (Rambus(trademark) Direct Dynamic Random Access Memory) device. While the RDRAM does have some characteristics which would be highly desirable for networking applications, such as high storage density, high data transfer capabilities and low amounts of delay on transitions between read operations and write operations, the RDRAM is generally considered as being optimized for computer applications. Like most DRAMs, the RDRAM is generally most efficient when dealing with long bursts of data from consecutive memory locations. To this end, sense amplifiers, used to transfer data to and from data banks in a RDRAM, are shared between memory banks. This design choice allows large chunks of data to be read out but also prevents an accessed bank, and any banks adjacent to the accessed bank, from being accessed for a given amount of time. Thus, if Bank A is accessed, that bank and any banks adjacent to it cannot be accessed for a time period that may be as long as the time it takes for three memory access operations.
This drawback of RDRAMs needs to be overcome so that the benefits of RDRAM can be harnessed for networking applications.
The present invention seeks to meet the above need by providing methods and devices for arranging memory access operations to minimize memory bank conflicts between such operations. A fixed pattern of memory access operations is implemented to minimize the effects of a transition between a read memory access operation and a write memory access operation. A write-read-gap (WRG) set pattern of a write memory access operation followed by a read memory access operation and then followed by a set gap when no memory access operation may be undertaken, meets the particular requirements of RDRAM. Within the WRG pattern, read addresses and write addresses are selected to minimize memory bank access conflicts. Such selections are assisted in increasing the efficiency of the memory access operations by defining a set frame size of a specific number of repetitions of the WRG pattern. All memory access operations are then rearranged to conform to the WRG pattern and, the repetitions of the WRG pattern are divided into frames having a size equal to that of the defined frame size. Within each frame, the read addresses to be accessed by read memory operations can be rearranged to minimize memory bank access conflicts with either write addresses to be accessed by write memory operations or other read addresses.
In a first aspect, the present invention seeks to provide a method of increasing the efficiency of memory access operations to a memory subsystem having multiple memory banks, the method comprising arranging memory access operations to the memory banks such that the memory access operations follow a predetermined repeating pattern, the repeating pattern comprising a write memory access operation followed by read memory access operation, each repetition of the repeating pattern being followed by a set time gap of during which no memory access operation may be undertaken, the set time gap being a fixed, predetermined amount of time.
In a second aspect the present invention provides a method of selecting a write address for a write memory access operation to avoid possible memory bank contention between successive memory access operation the method comprising selecting a write address based on the following criteria:
a) if a proximate read memory access operation is executed within a predetermined number of memory access operations from the write memory access operation, the write memory access operation accesses a group of memory banks different from a group of memory banks accessed by the proximate read memory access operation;
b) the write address accesses a memory bank chosen from a pool of memory banks, the pool excluding any of the following:
b1) memory banks accessed by an immediately preceding read memory access operation;
b2) memory banks to be accessed by an immediately succeeding read memory access operation;
b3) memory banks accessed by an immediately preceding write memory access operation; and
b4) memory banks immediately adjacent memory banks referred to in b1), b2) and b3);
c) the write memory access operation accesses a memory bank that is a least full memory bank in the pool of memory banks.
In a second aspect the present invention provides a method of increasing an efficiency of read memory access operations by avoiding possible memory bank contention between read memory access operations, the method comprising:
a) arranging memory access operations to the memory banks such that the memory access operation follow a predetermined repeating pattern, the repeating pattern comprising a write memory access operating followed by read memory access operation, each repetition of the repeating gap pattern being followed by fixed predetermined time interval during which no memory access operation may be undertaken;
b) defining a frame size of a predetermined fixed size, the frame size comprising a fixed number of repetitions of the repeating pattern;
c) dividing all memory access operations into frames having the frame size defined in step b);
d) dividing each frame into windows having a window size, each window having a first overlap of a least one instance of the repeating pattern with a preceding window and each window having a second overlap of at least one instance of the repeating pattern with a succeeding window; and
e) rearranging read memory access operations within each window such that memory addresses involved in the read memory access operations do not have bank conflicts with each other.